package cn.bellychang.bobo.sort;

import java.util.Random;

/**
 * @author ChangLiang
 * @date 2021/1/29
 */
public class SortUtil {

    enum SortAlgorithm {
        /**
         * 选择排序
         */
        selectionSort,
        /**
         * 插入排序
         */
        insertionSort,
        /**
         * 冒泡排序
         */
        bubbleSort,
        /**
         * 归并排序
         */
        mergeSort,
        /**
         * 快速排序
         */
        quickSort,
        /**
         * 堆排序
         */
        heapSort,
    }

    public static int[] sort(String sortAlgorithmName, int[] arr) {
        if (sortAlgorithmName.equals(SortAlgorithm.selectionSort.name())) {
            return selectionSort(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.insertionSort.name())) {
            return insertionSort2(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.bubbleSort.name())) {
            return bubbleSort(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.mergeSort.name())) {
            return mergeSort2(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.quickSort.name())) {
            return quickSort2(arr);
        } else {
            throw new RuntimeException(sortAlgorithmName + " is not supported now");
        }
    }

    public static int[] quickSort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr;
        }
//        quickSort2(arr, 0, arr.length - 1);
        quickSortThreeWays(arr, 0, arr.length - 1);
        return arr;
    }

    private static void quickSort2(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
//        int pivot = partition2(arr, begin, end);

        int pivot = partitionTwoWays(arr, begin, end);

//        System.out.println(pivot);
        quickSort2(arr, begin, pivot - 1);
        quickSort2(arr, pivot + 1, end);
    }

    private static void quickSortThreeWays(int[] arr, int begin, int end){
        if (begin >= end) {
            return;
        }

        // 得到的循环不变量是什么  [begin lt) < V   [lt, gt] = V (gt, end] > V
        TwoIndexWrapper twoIndexWrapper = partitionThreeWays(arr, begin, end);
        quickSortThreeWays(arr, begin, twoIndexWrapper.lt - 1);
        quickSortThreeWays(arr, twoIndexWrapper.gt + 1, end);
    }

    private static TwoIndexWrapper partitionThreeWays(int[] arr, int begin, int end){
        int pivot = end;

        int lt = begin;
        int gt = pivot - 1;
        int i = begin;
        int j = pivot - 1;

        while (true) {
            while (i < end && arr[i] < arr[pivot]) {
                lt++;
                i++;
            }
            while (j > begin && arr[j] > arr[pivot]) {
                gt--;
                j--;
            }
            while (j > lt && arr[j] == arr[pivot]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            lt++;
            gt--;
            swap(i, j, arr);
            i++;
            j--;
        }
        swap(i, pivot, arr);
        return new TwoIndexWrapper(lt, gt);
    }

    static class TwoIndexWrapper{
        int lt;
        int gt;
        public TwoIndexWrapper(int lt, int gt) {
            this.lt = lt;
            this.gt = gt;
        }
    }

    private static int partitionTwoWays(int[] arr, int begin, int end) {
/*        Random random = new Random();
        int pivot = random.nextInt(end - begin + 1) + begin;
        swap(pivot, end, arr);
        pivot = end;*/

        int pivot = end;

        int i = begin;
        int j = pivot - 1;

        // 循环不变量 arr[begin, i) <= v  && arr(i, end] >=v && i == v
        while (true) {
            while (i < end && arr[i] < arr[pivot]) {
                i++;
            }
            while (j > begin && arr[j] > arr[pivot]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(i, j, arr);
            i++;
            j--;
        }
        swap(i, pivot, arr);
        return i;
    }

    private static int partition2(int[] arr, int begin, int end) {
        Random random = new Random();
        int pivot = random.nextInt(end - begin + 1) + begin;
        swap(pivot, end, arr);
        pivot = end;

        int i = begin;
        while (i < end && arr[i] <= arr[pivot]) {
            i++;
        }
        int j = i;
        while (j < end) {
            if (arr[j] <= arr[pivot]) {
                swap(i, j, arr);
                i++;
            }
            j++;
        }
        swap(i, pivot, arr);
        return i;
    }

    private static int[] mergeSort2(int[] arr) {

        if (arr == null || arr.length == 0) {
            return arr;
        }

        int[] temp = new int[arr.length];

        mergeSort2(arr, temp, 0, arr.length - 1);

        return arr;
    }

    private static void mergeSort2(int[] arr, int[] temp, int begin, int end) {

        if (begin == end) {
            return;
        }
        int mid = ((end - begin) >> 1) + begin;
        mergeSort2(arr, temp, begin, mid);
        mergeSort2(arr, temp, mid + 1, end);
        merge2(arr, temp, begin, mid, end);
    }

    private static void merge2(int[] arr, int[] temp, int begin, int mid, int end) {
        int i = begin;
        int j = mid + 1;
        int index = begin;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
        while (j <= end) {
            temp[index++] = arr[j++];
        }
        System.arraycopy(temp, begin, arr, begin, end - begin + 1);
    }

    private static int[] insertionSort2(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(j, j - 1, arr);
                }
            }
        }
        return arr;
    }

    private static int[] bubbleSort2(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(j, j + 1, arr);
                }
            }
        }
        return arr;
    }

    private static int[] quickSort(int[] arr) {
        if (arr.length == 0) {
            return arr;
        }
        quickSort(0, arr.length - 1, arr);
        return arr;
    }

    private static void quickSort(int begin, int end, int[] arr) {
        if (begin >= end) {
            return;
        }
        int pivot = partition(begin, end, arr);
        quickSort(begin, pivot - 1, arr);
        quickSort(pivot + 1, end, arr);
    }

    private static int partition(int begin, int end, int[] arr) {
        int pivot = end;
        int i = begin;
        int j = begin;
        while (true) {
            if (arr[i] < arr[pivot]) {
                i++;
                j = i + 1;
            } else {

                while (j < end && arr[j] >= arr[pivot]) {
                    j++;
                }

                if (j >= end) {
                    break;
                }

                swap(i, j, arr);
                i++;
                j++;
            }
        }
        swap(i, pivot, arr);
        return i;
    }

    private static int[] mergeSort(int[] arr) {
        if (arr.length == 0) {
            return arr;
        }

        int[] tempArr = new int[arr.length];
        doMerge(arr, tempArr, 0, arr.length - 1);
        return arr;
    }

    private static void doMerge(int[] arr, int[] tempArr, int begin, int end) {
        if (begin == end) {
            return;
        }
        int mid = begin + ((end - begin) >> 2);
        doMerge(arr, tempArr, begin, mid);
        doMerge(arr, tempArr, mid + 1, end);
        merge(arr, tempArr, begin, mid, end);
    }

    private static void merge(int[] arr, int[] tempArr, int begin, int mid, int end) {
        int i = begin;
        int j = mid + 1;
        int k = begin;
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j]) {
                tempArr[k++] = arr[i++];
            } else {
                tempArr[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            tempArr[k++] = arr[i++];
        }
        while (j <= end) {
            tempArr[k++] = arr[j++];
        }
        for (k = begin; k <= end; k++) {
            arr[k] = tempArr[k];
        }
    }


    private static int[] bubbleSort(int[] arr) {
        // 如果本身就是有序的 那么通过这个boolean值 在O(N)时间复杂度内就完成了
        boolean hasChange = true;
        for (int i = 0; i < arr.length - 1 && hasChange; i++) {
            hasChange = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(j, j + 1, arr);
                    hasChange = true;
                }
            }
        }
        return arr;
    }

    private static int[] insertionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int temp = i;
            int j = i - 1;
            while (j >= 0 && arr[j] > arr[temp]) {
                swap(j, temp, arr);
                j--;
                temp--;
            }
        }
        return arr;
    }

    private static int[] selectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = findMin(i, arr);
            if (i != minIndex) {
                swap(i, minIndex, arr);
            }
        }
        return arr;
    }

    private static void swap(int i, int j, int[] arr) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int findMin(int begin, int[] arr) {
        int minIndex = begin;
        for (int i = begin + 1; i < arr.length; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    public static <E extends Comparable<E>> E[] sort(String sortAlgorithmName, E[] arr) {
        if (sortAlgorithmName.equals(SortAlgorithm.selectionSort.name())) {
            return selectionSort(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.insertionSort.name())) {
            return insertionSort(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.bubbleSort.name())) {
            return bubbleSort3(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.mergeSort.name())) {
            return mergeSort(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.quickSort.name())) {
            return quickSort(arr);
        } else if (sortAlgorithmName.equals(SortAlgorithm.heapSort.name())) {
            return heapSort(arr);
        } else {
            throw new RuntimeException(sortAlgorithmName + " is not supported now");
        }
    }

    private static <E extends Comparable<E>> E[] heapSort(E[] arr) {

        // 姑且这里认为arr是满的
        int size = arr.length - 1;
        buildHeap(arr, size);

        while (size > 1) {
            swap(1, size, arr);
            size--;
            heapify(arr, size, 1);
        }
        return arr;
    }

    private static <E extends Comparable<E>> void heapify(E[] arr, int size, int index) {
        while (true) {
            int maxPos = index;
            if (index * 2 <= size && arr[index * 2].compareTo(arr[maxPos]) > 0) {
                maxPos = index * 2;
            }
            if (index * 2 + 1 <= size && arr[index * 2 + 1].compareTo(arr[maxPos]) > 0) {
                maxPos = index * 2 + 1;
            }
            if (maxPos == index) {
                break;
            }
            swap(maxPos, index, arr);
            index = maxPos;
        }
    }

    private static <E extends Comparable<E>> void buildHeap(E[] arr, int size) {

        // 对下标从 size/2 开始到 1 的数据进行堆化
        // 下标是 size/2+1 到 size 的节点是叶子节点，我们不需要堆化
        for (int i = size / 2; i >= 1; i--) {
            heapify(arr, size, i);
        }
    }

    /**
     * 计数排序
     *
     * @param arrA 假设数组中存储的都是非负整数
     * @param
     * @return
     */
    public static int[] countingSort(int[] arrA) {
        if (arrA.length <= 1) {
            return arrA;
        }

        // 查找数组中数据的范围
        int max = arrA[0];
        for (int i = 1; i < arrA.length; i++) {
            if (max < arrA[i]) {
                max = arrA[i];
            }
        }

        // 申请一个计数数组 下标大小[0, max]
        int[] arrC = new int[max + 1];

        // 计算每个元素的个数 放入arrC
        for (int i = 0; i < arrA.length; i++) {
            arrC[arrA[i]]++;
        }

        int temp = 0;
        // 依次累加
        for (int i = 0; i < arrC.length; i++) {
            arrC[i] += temp;
            temp = arrC[i];
        }

        // 结果数组arrR 存储排序之后的结果
        int[] arrR = new int[arrA.length];
        // 注意：这里从后向前是为了保证稳定性
        for (int i = arrA.length - 1; i >= 0; i--) {
            // arrC[arrA[i]代表有多少个小于等于arrA[i]这个元素的值
            // 减去1 代表其应该放在arrR的哪个index( arrR中index从0开始)
            arrR[arrC[arrA[i]] - 1] = arrA[i];
            // 要维护arrC数组
            arrC[arrA[i]] -= 1;
        }
        return arrR;
    }

    private static <E extends Comparable<E>> E[] quickSort(E[] arr) {
        if (arr.length == 0) {
            return arr;
        }
        quickSort(0, arr.length - 1, arr);
        return arr;
    }

    private static <E extends Comparable<E>> void quickSort(int beginIndex, int endIndex, E[] arr) {

        // 注意这里要大于等于 如果pivot是子数组中最前面的值pivotIndex-1 overflow了 同理，如果pivot是子数组中最后面的值
        if (beginIndex >= endIndex) {
            return;
        }
        int pivotIndex = partition2(beginIndex, endIndex, arr);
        quickSort(beginIndex, pivotIndex - 1, arr);
        quickSort(pivotIndex + 1, endIndex, arr);
    }

    public static <E extends Comparable<E>> int partition(int beginIndex, int endIndex, E[] arr) {

        E pivot = arr[endIndex];

        // 循环不变量：pivot左侧是比其小的元素 pivot右侧是比其大的元素
        int biggerIndex = beginIndex;
        for (int i = beginIndex; i < endIndex; i++) {
            if (arr[biggerIndex].compareTo(pivot) > 0) {
                E temp = arr[biggerIndex];
                // 搬移数据 耗时
                System.arraycopy(arr, biggerIndex + 1, arr, biggerIndex, endIndex - biggerIndex);
                // 这种方式不涉及交换 保证了稳定性
                arr[endIndex] = temp;
            } else {
                biggerIndex++;
            }
        }
        System.out.println("the " + biggerIndex + " element is " + pivot);
        return biggerIndex;
    }


    /**
     * 通过游标 i 把 A[beginIndex…endIndex-1] 分成两部分
     * A[beginIndex…i-1] 的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i…endIndex-1] 是“未处理区间”
     * <p>
     * 每次都从未处理的区间 A[i…endIndex-1] 中取一个元素 A[j]
     * 与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i] 的位置
     *
     * @param beginIndex
     * @param endIndex
     * @param arr
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int partition2(int beginIndex, int endIndex, E[] arr) {
        E pivot = arr[endIndex];
        // 循环不变量 维护已处理区间 和 未处理区间
        int i = beginIndex;
        int j = beginIndex;
        while (j < endIndex) {
            if (arr[j].compareTo(pivot) < 0) {
                swap(i, j, arr);
                i++;
            }
            j++;
        }
        swap(i, j, arr);
        System.out.println("the " + i + " element is " + pivot);
        return i;
    }

    private static <E extends Comparable<E>> E[] mergeSort(E[] arr) {
        if (arr.length == 0) {
            return arr;
        }
        E[] target = (E[]) new Comparable[arr.length];
        mergeSort2(0, arr.length - 1, arr, target);
        return target;
    }

    private static <E extends Comparable<E>> void mergeSort2(int beginIndex, int endIndex, E[] arr, E[] target) {
        if (beginIndex == endIndex) {
            target[beginIndex] = arr[beginIndex];
            return;
        }
        int middle = (endIndex - beginIndex) / 2 + beginIndex;
        mergeSort2(beginIndex, middle, arr, target);
        mergeSort2(middle + 1, endIndex, arr, target);
        // merge 如何合并两个有序的数组
        int middleEnd = middle;

        // 优化1：在merge的时候，判断一下前一个数组最后一个元素和后一个数组最前面一个元素的大小关系
        if (arr[middle + 1].compareTo(arr[middle]) > 0) {
            for (int i = beginIndex; i <= endIndex; i++) {
                target[i] = arr[i];
            }
        } else {
            for (int i = middle + 1; i <= endIndex; i++) {
                merge(beginIndex, middleEnd, target[i], target);
                middleEnd++;
            }
        }
    }

    private static <E extends Comparable<E>> void mergeSort(int beginIndex, int endIndex, E[] arr, E[] target) {
        if (beginIndex == endIndex) {
            target[beginIndex] = arr[beginIndex];
            return;
        }
        int middle = (endIndex - beginIndex) / 2 + beginIndex;
        mergeSort(beginIndex, middle, arr, target);
        mergeSort(middle + 1, endIndex, arr, target);
        // merge 如何合并两个有序的数组
        int middleEnd = middle;

        for (int i = middle + 1; i <= endIndex; i++) {
            merge(beginIndex, middleEnd, target[i], target);
            middleEnd++;
        }
    }

    private static <E extends Comparable<E>> void merge(int beginIndex, int middle, E value, E[] target) {
        for (int j = middle; j >= beginIndex; j--) {
            if (target[j].compareTo(value) <= 0) {
                target[j + 1] = value;
                return;
            } else {
                target[j + 1] = target[j];
            }
        }
        target[beginIndex] = value;
    }


    private static <E extends Comparable<E>> E[] bubbleSort(E[] arr) {
        // 当i每次自增1的时候：分为未排序部分[0, arr.length - i) 和已排序部分[arr.length - i, arr.length)
        // 循环不变量 保证上面的两部分

        // i还有另一种含义 就是有多少个元素已经排好序了 这个在i不自增1的时候是有效的

        // 这里只需要进行n-1轮循环就可以 因为最后一轮只有一个元素了
        for (int i = 0; i < arr.length - 1; ) {
            // 内层循环一次swap都没有 说明已经是有序的了
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(j, j + 1, arr);
                }
            }
        }
        return arr;
    }

    private static <E extends Comparable<E>> E[] bubbleSort2(E[] arr) {
        // 当i每次自增1的时候：分为未排序部分[0, arr.length - i) 和已排序部分[arr.length - i, arr.length)
        // 循环不变量 保证上面的两部分

        // i还有另一种含义 就是有多少个元素已经排好序了 这个在i不自增1的时候是有效的

        // 这里只需要进行n-1轮循环就可以 因为最后一轮只有一个元素了
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层循环一次swap都没有 说明已经是有序的了
            boolean noSwap = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(j, j + 1, arr);
                    noSwap = false;
                }
            }
            // 这里是关键点
            if (noSwap) {
                break;
            }
        }
        return arr;
    }

    private static <E extends Comparable<E>> E[] bubbleSort3(E[] arr) {
        // 当i每次自增1的时候：分为未排序部分[0, arr.length - i) 和已排序部分[arr.length - i, arr.length)
        // 循环不变量 保证上面的两部分

        // i还有另一种含义 就是有多少个元素已经排好序了 这个在i不自增1的时候是有效的

        // 这里只需要进行n-1轮循环就可以 因为最后一轮只有一个元素了
        for (int i = 0; i < arr.length - 1; ) {
            // 内层循环一次swap都没有 说明已经是有序的了
            int lastSwapIndex = 0;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(j, j + 1, arr);
                    lastSwapIndex = j + 1;
                }
            }
            // 这里是关键点
            i = arr.length - lastSwapIndex;
            if (lastSwapIndex == 0) {
                break;
            }
        }
        return arr;
    }

    private static <E extends Comparable<E>> E[] insertionSort(E[] arr) {
        // 分已排序区间和未排序区间
        // // <font color='red'>循环不变量</font>：arr[i...n)未排序，arr[0...i)已排序
        for (int i = 0; i < arr.length - 1; i++) {
            doInsertionSort(i, arr, arr[i + 1]);
        }
        return arr;
    }

    /**
     * 在已排序区间从后向前找到第一个比value小的值 此时的index就是要插入的index
     *
     * @param beginIndex 已排序区的最大index
     * @param arr
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> void doInsertionSort(int beginIndex, E[] arr, E value) {
        for (int i = beginIndex; i >= 0; i--) {
            if (arr[i].compareTo(value) <= 0) {
                arr[i + 1] = value;
                return;
            } else {
                //
                arr[i + 1] = arr[i];
            }
        }
        arr[0] = value;
    }

    private static <E extends Comparable<E>> E[] selectionSort(E[] arr) {

        // 分已排序区间和未排序区间
        // <font color='red'>循环不变量</font>：arr[i...n)未排序，arr[0...i)已排序
        for (int i = 0; i < arr.length; i++) {
            int minIndex = getMinIndex(i, arr);
            if (minIndex != i) {
                swap(i, minIndex, arr);
            }
        }
        return arr;
    }

    /**
     * 交换 从未排序区间中找到最小的元素，将其放到已排序区间的末尾
     *
     * @param fromIndex
     * @param toIndex
     * @param arr
     * @param <E>
     */
    private static <E> void swap(int fromIndex, int toIndex, E[] arr) {
        E temp = arr[fromIndex];
        arr[fromIndex] = arr[toIndex];
        arr[toIndex] = temp;
    }

    /**
     * 找到未排序部分的最小值
     *
     * @param beginIndex 未排序部分的起始index
     * @param arr
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int getMinIndex(int beginIndex, E[] arr) {
        if (beginIndex < 0 || beginIndex >= arr.length) {
            throw new RuntimeException("array beginIndex is not valid");
        }
        if (beginIndex == arr.length - 1) {
            return beginIndex;
        }
        int minIndex = beginIndex;
        for (int i = beginIndex + 1; i < arr.length; i++) {
            if (arr[minIndex].compareTo(arr[i]) > 0) {
                minIndex = i;
            }
        }
        return minIndex;
    }
}
